/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-08-20
 * Time: 14:11
 */
//https://leetcode.cn/problems/sqrtx/
public class Test {
    public static int mySqrt(int x) {
        int p1=0,p2=x,p=(p1+p2)/2;
        while(p1<p2){
            long n=(long)p*p;
            if(n<=x && (n+p+p+1)>x){
                return p;
            }
            if(n<x){
                p1=p+1;
            }
            else{
                p2=p-1;
            }
            p=(p1+p2)/2;
        }
        return p;
    }

    public static void main(String[] args) {
        int x=2147395599;
        System.out.println(mySqrt(x));
    }
}
